

"""
724.寻找数组的中心下标
https://leetcode.cn/problems/find-pivot-index

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
"""

from typing import List


class Solution:
    def method1(self, nums: List[int]) -> int:
        """
        常规,气氛左右两个子列表。
        1遍循环，但是加的次数太多，比较慢 
        """
        size = len(nums)
        for i in range(size):
            left = nums[:i]
            right = nums[i+1:]
            if sum(left) == sum(right):
                return i

        return -1

    def method2(self, nums: List[int]) -> int:
        """
        采用preSum的方式，预计算，后面只要减法就好了
        这个在数组中，要掌握！！！

        用于在数组中快速求解[i...j]的和
        sums = [0]*(size+1)  # sums[i]存放[0...i]的和
        for i in range(1, size+1):
            sums[i] = sums[i-1] + nums[i-1]
        """
        size = len(nums)
        sum_ = sum(nums)

        presum = 0
        for i in range(size):
            if presum == sum_ - nums[i] - presum:
                return i
            presum += nums[i]
        return -1

    def pivotIndex(self, nums: List[int]) -> int:
        size = len(nums)
        if size <= 1:
            return 0

        return self.method2(nums)


def test():
    obj = Solution()
    nums = [1, 7, 3, 6, 5, 6]
    # nums = [2, 1, -1]
    res = obj.pivotIndex(nums)
    print(res)


if __name__ == "__main__":
    test()
